package exercises.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/">
 * 352. 将数据流变为多个不相交区间</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
 * <p>
 * 实现 SummaryRanges 类：
 * <li>SummaryRanges() 使用一个空数据流初始化对象。</li>
 * <li>void addNum(int val) 向数据流中加入整数 val 。</li>
 * <li>int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。</li>
 *
 * @author or2
 * @date 2021年10月09日 时间: 7:40
 */
public class No352 {

    public static class SummaryRanges {

        short[] union;

        public SummaryRanges() {
            union = new short[10_000 + 1];
            Arrays.fill(union, (short) -1);
        }

        public void addNum(int val) {
            if (val == 0) {
                if (union[1] != -1) {
                    union[0] = union[1];
                    union[1] = 0;
                } else
                    union[0] = 0;
                return;
            }

            if (val == 10_000) {
                if (union[9_999] != -1) {
                    union[10_000] = union[9_999];
                    union[9_999] = 10_000;
                } else
                    union[10_000] = 10_000;
                return;
            }

            if (union[val - 1] != -1) {
                short head = union[val - 1];
                union[head] = (short) val;
                union[val] = head;
            }

            if (union[val + 1] != -1) {
                short end = union[val + 1];
                int head = findHead((short) val);
                union[head] = end;
                union[val + 1] = (short) head;
            } else
                union[val] = (short) val;
        }

        private short findHead(short index) {
            if (union[index] == -1)
                return index;
            while (union[index] < index)
                index = union[index];
            return index;
        }

        public int[][] getIntervals() {
            var res = new ArrayList<int[]>();
            for (short i = 0, length = (short) (union.length - 1); i < length; i++) {
                if (union[length] == -1)
                    continue;
                short head = findHead(length);
                res.add(new int[]{head, length});
                length = head;
            }

            return res.toArray(int[][]::new);
        }

        public int[][] getIntervals2() {
            var res = new ArrayList<int[]>();
            for (short i = 0, length = (short) (union.length - 1); i < length; i++) {
                if (union[i] == -1)
                    continue;
                short end = union[i];
                res.add(new int[]{i, end});
                i = end;
            }

            return res.toArray(int[][]::new);
        }
    }

    //—————————————————— 版本一 —— 失败 ————————————————————————————————————————————————————————————————————————

    public static class SummaryRanges2 {

        short[] union;

        ArrayList<int[]> res;

        public SummaryRanges2() {
            union = new short[10_000 + 1];
            Arrays.fill(union, (short) -1);
            res = new ArrayList<>();
        }

        public void addNum(int val) {
            int location = binarySearch(val);
            if (location == -1) {
                res.add(new int[]{val, val});
                union[val] = (short) val;
                return;
            } else if (location == res.size()) {
                if (union[val - 1] != -1) {
                    short head = findHead((short) (val - 1));
                    union[head] = (short) val;
                    union[val] = head;
                    res.get(location - 1)[1] = val;
                } else {
                    res.add(new int[]{val, val});
                    union[val] = (short) val;
                }
                return;
            } else {
                int[] range = res.get(location);
                if (range[0] <= val && val <= range[1])
                    return;
            }

            if (val == 0) {
                if (union[1] != -1) {
                    union[0] = union[1];
                    union[1] = 0;
                    res.get(location)[0] = 0;
                } else {
                    union[0] = 0;
                    res.add(location, new int[]{0, 0});
                }
                return;
            }

            if (val == 10_000) {
                if (union[9_999] != -1) {
                    union[10_000] = union[9_999];
                    union[9_999] = 10_000;
                    res.get(location)[1] = 10_000;
                } else {
                    union[10_000] = 10_000;
                    res.add(new int[]{10_000, 10_000});
                }
                return;
            }

            if (union[val - 1] == -1 && union[val + 1] == -1) {
                union[val] = (short) val;
                res.add(location, new int[]{val, val});
                return;
            }

            if (union[val - 1] != -1) {
                short head = findHead((short) (val - 1));
                union[head] = (short) val;
                union[val] = head;
                res.get(location - 1)[1] = val;
            }

            if (union[val + 1] != -1) {
                short end = union[val + 1];
                int head = findHead((short) val);
                if (head != val) {
                    res.get(location - 1)[1] = end;
                    res.remove(location);
                } else
                    res.get(location)[0] = val;
                union[head] = end;
                union[val + 1] = (short) head;
            }
        }

        public int[][] getIntervals() {
            return res.toArray(int[][]::new);
        }

        private short findHead(short index) {
            if (union[index] == -1)
                return index;
            while (union[index] < index)
                index = union[index];
            return index;
        }

        private int binarySearch(int value) {
            int left = 0, right = res.size(), mid;
            if (right == 0)
                return -1;
            while (left < right) {
                mid = left + (right - left >> 1);
                int[] range = res.get(mid);
                if (range[0] > value)
                    right = mid;
                else if (range[1] < value)
                    left = mid + 1;
                else
                    return mid;
            }
            return left;
        }

    }

    //—————————————————— 版本二 —— 成功 ————————————————————————————————————————————————————————————————————————

    //如果使用 TreeSet 呢？
/*
    class SummaryRanges3 {

        short[] union;
        TreeSet<int[]> res;

        public SummaryRanges3() {
            union = new short[10_001];
            res = new TreeSet<>((Comparator.comparingInt(o -> o[0])));
        }

        public void addNum(int val) {

        }

        public int[][] getIntervals() {

        }
    }
*/

}
